#ifndef AST_H
#define AST_H

/** @file ast.h
* Declares data structures and functions to construct an Abstract Syntax Tree.
* Below is an example of how one might use these functions to create an AST,
* add nodes and print the result.
* @code
*    struct Node* root;
*    struct MemBlockInfo* mem;
*    struct Node* expr=NULL;
*    struct Node* pathexpr=NULL;
*    struct Node* andexpr=NULL;
*    struct Node* predicate=NULL;
*
*    mem=memInit(sizeof(struct Node));      //reserve a block of memory
*
*    expr=newRule(mem, Expr,0);             //Expr
*    root=expr;                             //make Expr the root of the AST
*    pathexpr=newRule(mem,PathExpr,0);      //PathExpr
*    andexpr=newRule(mem,AndExpr,0);        //AndExpr
*    predicate=newRule(mem,Predicate,0);    //Predicate
*
*    nodeAppendChild(mem,expr,pathexpr);    //Expr->PathExpr    [child]
*    nodeInsertRight(expr,predicate,mem);   //Expr, Predicate   [sibling]
*    nodeInsertRight(pathexpr,andexpr,mem); //PathExpr, AndExpr [sibling]
*
*    printXPath10(root,PRINT_TEXT);         //print the AST
* @endcode
* @b Result:
* @code
*    Expr
*       PathExpr
*       AndExpr
*    Predicate 
* @endcode
*
* @author Victor Petrov <victor_petrov@harvard.edu>
* @date   Feb 26, 2011
* @cond
*------------------------------------------------------------------------------
* LEGAL:
*------------------------------------------------------------------------------
*
* Copyright (c) 2011, The President and Fellows of Harvard College
* Copyright (c) 2011, The Neuroinformatics Research Group at Harvard University
* All rights reserved.
*
* License: New BSD License   <http://creativecommons.org/licenses/BSD/>
*-------------------------
* Redistribution and use in source and binary forms, with or without 
* modification, are permitted provided that the following conditions are met:
*
*	Redistributions of source code must retain the above copyright notice, 
*	this list of conditions and the following disclaimer.
*
*	Redistributions in binary form must reproduce the above copyright notice, 
*	this list of conditions and the following disclaimer in the documentation
*	and/or other materials provided with the distribution.
*
*	Neither the name of the Neuroinformatics Research Group at Harvard, nor 
*	the names of its contributors may be used to endorse or promote products 
*	derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
* POSSIBILITY OF SUCH DAMAGE.
*------------------------------------------------------------------------------
* vim: ts=4
*------------------------------------------------------------------------------
* @endcond
*/

#include "tokens.h"         /* enum yytokentype */
#include "nonterminals.h"   /* TokenNames[] */
#include "memblock.h"       /* memGet() */

/** The types of Nodes available */
enum NodeType
{
    NODE_TOKEN,     /**< A token */
    NODE_RULE,      /**< A rule from the grammar */
    NODE_STRING     /**< A value node */
};

enum QuoteType
{
    NO_QUOTES=0,        /**< No quotes */
    SINGLE_QUOTES='\'', /**< Single quotes */
    DOUBLE_QUOTES='"'   /**< Double quotes */
};


/** The kinds of Step nodes available */
enum StepKind
{
    STEP_UNKNOWN,   /**< An unknown Step kind */
    STEP_FORWARD,   /**< A forward Step: child::, descendent::, e/b/c */
    STEP_REVERSE,   /**< A reverse Step: ancestor::, preceding::  */
    STEP_CURRENT    /**< A Step that refers to the current element: */
};

/** A leaf (or root) in the Abstract Syntax Tree.
* Encapsulates information about immediate children and siblings,
* about the value it holds and other metadata
*/
struct Node
{
    struct Node* parent;        /**< The parent Node */
    struct Node* left;          /**< The preceding sibling Node */
    struct Node* right;         /**< The following sibling Node */
    struct Node* first;         /**< The first sibling Node */
    struct Node* last;          /**< The last sibling Node */
    unsigned int children;      /**< Number of children */

    union
    {
        enum yytokentype t;     /**< For @c tokens, the token type */
        enum NonTerminals nt;   /**< For @c nonterminals, the rule name */
        void* p;                /**< For @c values, pointer to a char* */
    } data;                     /**< The value of the Node */

    enum NodeType type;         /**< The type of this Node */
	const char* name;           /**< The name of the token or rule */
    enum StepKind stepKind;     /**< For Step nodes, the kind of Step */

    union
    {
        int isPath;             /**< StepExpr: compatibility with XPath 2.1 */
        enum QuoteType quotes;  /**< Literal: the type of quotes used */
    } extra;                    /**< Properties of Step nodes, String nodes */
};

/** W3C AST compatibility */
enum XPathVersion
{
    XPATH_10,   /**< XPath 1.0 AST */
    XPATH_20,   /**< XPath 2.0 AST */
    XPATH_21    /**< XPath 2.1 AST */
};


/** @name Functions that generate Nodes
*   @{
*/

/** Creates a NODE_TOKEN node.
* @param[in] mem   MemBlockInfo struct handling all memory operations
* @param[in] token The token the new node will represent
* @param[in] name  The name of the token
* @return A pointer to a new Node
*/
struct Node* newToken(struct MemBlockInfo* mem, enum yytokentype token, 
                      const char* const name);

/** Creates a NODE_RULE node with, optionally, its child Nodes.
* @param[in] mem       MemBlockInfo struct handling all memory operations
* @param[in] rule      The rule the new node will represent
* @param[in] children  The number of children for the new node
* @param[in] ...       The children (struct Node*)
* @return A pointer to a new Node
*/
struct Node* newRule(struct MemBlockInfo* mem, enum NonTerminals rule,
                     unsigned int children, ... );

/** Creates a new NODE_STRING node that represents an NCName value 
* @param[in] mem    MemBlockInfo struct handling all memory operations
* @param[in] value  The string value
* @return A pointer to a new Node
* @warning Caller must make sure value is valid
*/
struct Node* newNCName(struct MemBlockInfo* mem, char* value);

/** Creates a new NODE_STRING node that represents a Literal value 
* @param[in] mem    MemBlockInfo struct handling all memory operations
* @param[in] value  The string value
* @return A pointer to a new Node
* @warning Caller must make sure @c value is valid
*/
struct Node* newLiteral(struct MemBlockInfo* mem, char* value, 
                        enum QuoteType quotes);

/**@}*/

/** @name Functions that append / insert Nodes
* @{
*/

/** Appends a Node child to a node.
* @param[in] mem    MemBlockInfo struct handling all memory operations
* @param[in] node   The parent node
* @param[in] child  The child node
*/
void nodeAppendChild(struct MemBlockInfo* mem, struct Node* node, 
                     struct Node* child);

/** Appends multiple Node siblings to another Node
* @param[in] mem      MemBlockInfo struct handling all memory operations
* @param[in] node     The node to append siblings to
* @param[in] siblings Number of sibling nodes to append
* @param[in] ...      The siblings (struct Node*)
*/
void nodeAppendSiblings(struct MemBlockInfo* mem, struct Node* node,
                        unsigned int siblings, ... );

/** Inserts a node (and all its siblings) as a direct sibling of @c node
* @param[in] mem      MemBlockInfo struct handling all memory operations
* @param[in] node     The reference node
* @param[in] sibling  The new sibling
* @warning @c sibling must not already have a parent and should not already
*          be a sibling of @c node
*/
void nodeInsertRight(struct MemBlockInfo* mem, struct Node* node,
                     struct Node* sibling);

/** Changes the parent of a node and all its siblings.
* @param[in] child   The child node
* @param[in] parent  The new parent
* @warning @c parent is allowed to be NULL
*/
void nodeReparent(struct Node* child, struct Node* parent);

/**@}*/

/** @name Functions that search, verify and count Nodes
* @{
*/

/** Retrieves the @b first sibling of a node
* @param[in] child  The node
* return The first sibling of @c child
*/
struct Node* nodeGetFirstSibling(struct Node* child);

/** Retrieves the @b last sibling of a node
* @param[in] child  The node
* return The last sibling of @c child
*/
struct Node* nodeGetLastSibling (struct Node* child);

/** Counts the number of siblings from the left and from the right
* @param[in] node The node who's siblings need to be counted
* @result Number of siblings found
*/
unsigned int nodeCountSiblings  (struct Node* node);

/** Checks whether a @c node has a specific @c sibling
* @param[in] node     The node who's siblings need to be counted
* @param[in] sibling  The sibling to search for
* @result @c 1 on Success, @c 0 on Failure
*/
int nodeHasSibling(struct Node* node, struct Node* sibling);

/** Check if @c node is a rule of type specified by @c rule
* @param[in] node  The node to check
* @param[in] rule  The rule to check against
* @return @c 1 on Success, @c 0 on Failure
*/
int isRule(const struct Node* node, enum NonTerminals rule);

/** Checks whether a @c node contains a @c rule as a child
* @param[in] node  The node to check
* @param[in] rule  The rule to check against
* @return @c 1 on Success, @c 0 on Failure
*/
int hasRule(const struct Node* node, enum NonTerminals rule);

/** Check if @c node is a token of type specified by @c token
* @param[in] node   The node to check
* @param[in] token  The token to check against
* @return @c 1 on Success, @c 0 on Failure
*/
int isToken(const struct Node* node, enum yytokentype token);

/** Checks whether a @c node contains a @c token as a child
* @param[in] node   The node to check
* @param[in] token  The token to check against
* @return @c 1 on Success, @c 0 on Failure
*/
int hasToken(const struct Node* node, enum yytokentype token);

/**@}*/
#endif

